/*
 * @lc app=leetcode.cn id=279 lang=typescript
 *
 * [279] 完全平方数
 */

// @lc code=start
function numSquares(n: number): number {
  // 从0开始，逐行搜索下去，直到找到和为n的层数
  const queue: number[] = [0];
  // 记录访问过的节点
  const hash: Set<number> = new Set([0]);

  let ans = 0;
  while (queue.length) {
    ans++;
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      // 拿出值来计算
      const num = queue.shift();
      for (let j = 1; j <= n; j++) {
        // value始终是平方和
        const value = num + j * j;
        // 等于n就是找到了，直接返回
        if (value === n) return ans;
        // 大于n了，当前数字不适合，终止循环
        if (value > n) break;
        // 记录到已经计算过的值，hash防止重复计算
        if (!hash.has(value)) {
          queue.push(value);
          hash.add(value);
        }
      }
    }
  }

  return ans;
}
// @lc code=end
